package com.cat.graphTheory;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/design-graph-with-shortest-path-calculator/description/?envType=problem-list-v2&envId=cNHS7dSX
 * @create 2025/9/25 15:00
 * @since JDK17
 */

public class Graph {
    static List<int[]>[] g;
    static PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    static int[] dis;
    public Graph(int n, int[][] edges) {
        g = new List[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        dis = new int[n];
        for (var e : edges) {   // 建图
            addEdge(e);
        }
    }

    public void addEdge(int[] edge) {
        g[edge[0]].add(new int[]{edge[1], edge[2]});
    }

    public int shortestPath(int node1, int node2) {
        pq.clear();
        Arrays.fill(dis, Integer.MAX_VALUE);
        pq.add(new int[]{node1, 0});
        dis[node1] = 0;
        while (!pq.isEmpty()) {
            int[] p = pq.poll();
            if (p[0] == node2) {
                return p[1];
            }
            if (p[1] > dis[p[0]]) {
                continue;
            }
            for (var x : g[p[0]]) {
                if (p[1] + x[1] < dis[x[0]]) {
                    dis[x[0]] = p[1] + x[1];
                    pq.add(new int[]{x[0], dis[x[0]]});
                }
            }
        }

        return -1;
    }
}
